第十四天 Deadlocks(死結)--上

在我們講deadlock前，我們先來說說system model！system內包含了很多資源(resource)，而資源也有很多種型態。不管是哪種型態的資源，都有多個instance(像是有5個disk、不只1個Ｉ/Ｏ devices)。而process用資源時，要經過三個步驟：提出需求(request)、使用資源(use)、釋放資源(release)。

接下來回到deadlock身上！
要形成deadlock，必須同時滿足4個條件：

1. Mutual exclusion：
   一個resource一次只能被一個process用
2. Hold and wait：
   process至少取到一個resource，然後等其他process握住的resource
3. No preemption：
   釋放資源時，是process自願的，沒有被中斷
4. Circular wait：
   每個process都在等另一個process握住的resource釋放(例如：P1等P2、P2等P3、P3等P1)，這也代表single process不會有deadlock

我們可以運用Resource-Allocation Graph(RAG)，看system model有沒有deadlock。

Resource-Allocation Graph(RAG)的頂點分兩種，process跟resource ; edge也分兩種，request edge(process指向resource)和assignment edge(resource指向process)。
以下有兩個圖，第一個是有deadlock的RAG，第二個沒有：


如果RAG的圖中沒有cycle，那一定沒有deadlock;圖中有cycle，那會有兩種情形：1. 如果resource type中只有一個instance，則一定會有deadlock 2. 如果resource type中不止有一個instance，則不一定會有deadlock。

明天我們來說說處理deadlock的幾個方法！